package com.wfm.leetcode.editor.cn;

import java.util.Arrays;

/**
 * 方法一：动态规划
 * ij表示以下标[i,j]的字符串是否是回文
 * 因为某一个ij依赖于i+1 j-1 也就是依赖于下、左两个方向，所以得斜着遍历dp
 * 比如   i          j  这个字符串是否回文，取决于他内部是否是回文
 *         i+1  j-1
 * xxxxx表示没用到，因为不可能出现i比j大的这种字符
 * [true, false, false, true, false]
 * [xxxxx, true, true, false, false]
 * [xxxxx, xxxxx, true, false, false]
 * [xxxxx, xxxxx, xxxxx, true, false]
 * [xxxxx, xxxxx, xxxxx, xxxxx, true]
 *
 * 方法二是中心扩散法
 * 需要注意的是，要对每个数组元素都要执行中心扩散操作
 * 其中对一个元素执行中心扩散操作是：left i right
 * 判断num[left]==i,是left-- 长度+1
 * 判断num[right]==i,是right++ 长度+1
 * 然后判断nums[left]==num[right] 是的话，left-- right++,长度加2
 */
public class PFive最长回文子串{
//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
    public String longestPalindrome(String s) {
        int len = s.length();
        if (len < 2) {
            return s;
        }

        int maxLen = 1;
        int begin = 0;
        // dp[i][j] 表示 s[i..j] 是否是回文串
        boolean[][] dp = new boolean[len][len];
        // 初始化：所有长度为 1 的子串都是回文串
        for (int i = 0; i < len; i++) {
            dp[i][i] = true;
        }

        char[] charArray = s.toCharArray();
        // 递推开始
        // 先枚举子串长度
        for (int L = 2; L <= len; L++) {
            // 枚举左边界，左边界的上限设置可以宽松一些
            for (int i = 0; i < len; i++) {
                // 由 L 和 i 可以确定右边界，即 j - i + 1 = L 得
                int j = L + i - 1;
                System.out.println(i+"==="+j);
                // 如果右边界越界，就可以退出当前循环
                if (j >= len) {
                    break;
                }

                if (charArray[i] != charArray[j]) {
                    dp[i][j] = false;
                } else {
                    if (j - i < 3) {
                        dp[i][j] = true;
                    } else {
                        dp[i][j] = dp[i + 1][j - 1];
                    }
                }

                // 只要 dp[i][L] == true 成立，就表示子串 s[i..L] 是回文，此时记录回文长度和起始位置
                if (dp[i][j] && j - i + 1 > maxLen) {
                    maxLen = j - i + 1;
                    begin = i;
                }
            }
        }
        for (int i = 0; i < dp.length; i++) {
            System.out.println(Arrays.toString(dp[i]));
        }
        return s.substring(begin, begin + maxLen);

    }

//    public String longestPalindrome2(String s) {
//        if(s.length() == 0 || s == null) {
//            return "";
//        }
//
//        int strLen = s.length();
//        int left = 0;
//        int right = 0;
//        int maxLen = 0;
//        int maxStart = 0;
//        char[] charArray = s.toCharArray();
//
//        for(int i = 0; i < strLen; i++) {
//            left = i - 1;
//            right = i + 1;
//            int len = 1;
//            while(left >= 0 && charArray[left] == charArray[i]) {
//                left--;
//                len++;
//            }
//            while(right < strLen && charArray[right] == charArray[i]) {
//                right++;
//                len++;
//            }
//            while(left >= 0 && right < strLen && charArray[left] == charArray[right]) {
//                left--;
//                right++;
//                len += 2;
//            }
//            if(len > maxLen) {
//                maxLen = len;
//                maxStart = left;
//            }
//        }
//        return s.substring(maxStart + 1, maxStart + maxLen + 1);
//    }
}
//leetcode submit region end(Prohibit modification and deletion)

    public static void main(String[] args) { 
        Solution solution = new PFive最长回文子串().new Solution();
        System.out.println(solution.longestPalindrome("abbac"));
    }
}